package 每日一题;

import com.alibaba.fastjson.JSON;

public class No88合并两个有序数组 {

    /**
     * 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
     * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
     * 你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
     *
     * 示例 1：
     * 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
     * 输出：[1,2,2,3,5,6]
     * 示例 2：
     * 输入：nums1 = [1], m = 1, nums2 = [], n = 0
     * 输出：[1]
     *  
     * 提示：
     * nums1.length == m + n
     * nums2.length == n
     * 0 <= m, n <= 200
     * 1 <= m + n <= 200
     * -109 <= nums1[i], nums2[i] <= 109
     */

    public void merge(int[] nums1, int m, int[] nums2, int n) {

        if(nums2.length<1){
            return;
        }
        if(m==0){
            for (int i = 0; i < nums2.length; i++) {
                nums1[i]=nums2[i];
            }
            return;
        }

        //从后向前,就O(1)空间复杂度
        int index=nums1.length-1;
        int no1=m-1;
        int no2=n-1;

        while (index>=0&&no1>=0&&no2>=0){

            while (no1>=0&&nums1[no1]>nums2[no2]){
                nums1[index]=nums1[no1];
                no1--;
                index--;
            }

            while (no1>=0&&no2>=0&&nums1[no1]<nums2[no2]){
                nums1[index]=nums2[no2];
                no2--;
                index--;
            }

            if(no1>=0&&no2>=0&&nums1[no1]==nums2[no2]) {
                nums1[index] = nums2[no2];
                no2--;
                index--;
            }

        }

        if(no1>=0){
            for (int i = no1; i >= 0; i--,index--) {
                nums1[index]=nums1[i];
            }
        }
        if(no2>=0){
            for (int i = no2; i >= 0; i--,index--) {
                nums1[index]=nums2[i];
            }
        }

    }

    public static void main(String[] args) {
        No88合并两个有序数组 n=new No88合并两个有序数组();
        int[] arr1={2,0};
        int[] arr2={1};
        n.merge(arr1,1,arr2,1);
        System.out.println(JSON.toJSONString(arr1));
    }

}
